package com.duing.recu;

import java.util.Arrays;

/**
 * 递归规律
 * f(i) 到下标i位置的最佳方案
 * 偷 或 不偷 当前的值
 * f(i) = Math.max(f(i-1), (f(i-2) + nums[i]))
 * <p>
 * 递归出口
 * f(0) = nums[0]
 * f(1) = Math.max(nums[0],nums[1])
 */
public class Rob {

    public static void main(String[] args) {
        //                     0  1  2  3  4
        int[] nums = new int[]{2, 7, 9, 3, 1};
        int[] nums1 = new int[]{1, 2, 3, 5, 1};
        //System.out.println(rob(nums));
        //System.out.println("=============");
        System.out.println(robByDP(nums));

    }

    public static int rob(int[] nums) {
        return robByRecu(nums, nums.length - 1);
    }

    public static int robByRecu(int[] nums, int i) {
        if (i == 0) return nums[0];
        if (i == 1) return Math.max(nums[0], nums[1]);

        int A = robByRecu(nums, i - 1);
        int B = robByRecu(nums, i - 2) + nums[i];
        if (A > B) {
            System.out.println("F" + i + "的值 == F" + (i - 1) + "的值");
        } else {
            System.out.println("F" + i + "的值 == F" + (i - 2) + "的值加上自身 " + nums[i]);
        }
        return Math.max(A, B);
    }

    // {2, 7, 9, 3, 1}
    // F(0) = 2
    // F(1) = 7
    // F(2) = F(0) + 9 = 11
    // F(3) = F(2) = 11
    // F(4) = F(2) + 1 = 12
    public static int robByDP(int[] nums) {
        if (nums.length == 1) return nums[0];

        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[1], nums[0]);

        for (int i = 2; i < dp.length; i++) {
            int A = dp[i - 1];
            int B = dp[i - 2] + nums[i];
            dp[i] = Math.max(A, B);
        }
        //System.out.println(Arrays.toString(dp));
        return dp[dp.length - 1];
    }

    // 作业题： 最大子序和
    // [-2,1,-3,4,-1,2,1]
    // f(i)  当前位置i 结尾的最大子序的和
    //  对于n个元素的数组  包含f(0) f(1) .. f(n-1)的所有子序
    //  maxSubArray(n) = max[f(0),f(1) .. f(n-1)]
    // f(i-1) > 0  =>  A = f(i-1) + nums[i]
    //                 B = nums[i]

    // int max = Int.MIN;
    // f(0) = -2
    // f(1) = 1
    // f(2) = -2
    // f(3) = 4
    // f(4) = 3
    // f(5) = 5
    // f(6) = 6

    // [-2,-3,-1,2,1,-7]
    // f(0) = -2
    // f(1) = -3
    // f(2) = -1
    // f(3) = 2
    // f(4) = 3
    // f(5) = -4
}
